package utils;



public class LinkedList<T> {
	
	private Node<T> head;
	private Node<T> tail;
	private int _size;
	
	public LinkedList()
	{
		_size = 0;
		head = null;
		tail = null;
	}
	
	/* [] - [t] - n - []*/
	public Node<T> insertNext(Node<T> prev, T e)
	{
		Node<T> newNode = new Node<T>(e);
		Node<T> next = prev.next;
		newNode.prev = prev;
		newNode.next = next;
		prev.next = newNode;
		next.prev = newNode;
		if(tail == prev)
			tail = newNode;
		_size ++;
		return newNode;
	}
	
	/* [] - [] - n - [t] */
	public Node<T> insertPrev(Node<T> next, T e)
	{
		Node<T> newNode = new Node<T>(e);
		Node<T> prev = next.prev;
		newNode.prev = prev;
		newNode.next = next;
		prev.next = newNode;
		next.prev = newNode;
		if(head == next)
			head = newNode;
		_size ++;
		return newNode;
	}
	
	/** [] - [] - [tail] - n - ? **/
	public Node<T> addLast(T e)
	{
		if(tail == null)
		{
			tail = new Node<T>(e);
			tail.next = tail;
			tail.prev = tail;
			head = tail;
			_size ++;
		}
		else
		{
			insertNext(tail, e);
		}
		return tail;
	}
	
	public Node<T> addFirst(T e)
	{
		if(head == null)
		{
			head = new Node<T>(e);
			head.next = head;
			head.prev = head;
			tail = head;
			_size ++;
		}
		else
		{
			insertPrev(head, e);
		}
		return head;
	}
	
	public void remove(Node<T> n)
	{
		if(tail == null)
			return;
		
		if(head == n && tail ==n)
		{
			head = tail = null;
			_size --;
		}
		else
		{
			n.prev.next = n.next;
			n.next.prev = n.prev;
			
			if(head == n)
			{
				head = n.next;
			}
			else if(tail == n)
			{			
				tail = n.prev;
			}
			_size--;
		}
	}
	
	public void removeAll()
	{
		while(head != null)
		{
			remove(head);
		}
	}
	
	public ListIterator<T> listIterator()
	{
		if(head != null)			
			return new ListIterator<T>(head);
		else
			return null;
	}
	
	public int size()
	{
		return _size;
	}
		
	
}
